37
Explore Your Deductive Logic—Sudoku
37
If you have solved Sudoku puzzles, you know that the most important thing to con
sider when you are looking to fill an empty cell is what it cannot be—each column,
row, and 3 by 3 grid can have the numbers 1 to 9 only once. Hence, for each cell in
the 9 by 9 grid that already has a value, it provides an exclusion for the row, column,
and 3 by 3 grid that this cell identifies with.
Hence the program needs to keep track of these exclusions. We store these in a
structure called “Array”. An array is a way of storing variables so that we can refer
to them using rows and columns. We call this array a “cantbelist” to store each of the
numbers that it cannot be. We need three dimensions to store this—the row and the
column to refer to which cell in the 9 by 9 grid we are talking about are two of them.
The third dimension is the number that cell can’t be. Let’s take the example in Figure
3.3 to illustrate this:
7
3
2
4
5
5
2
3
4
7
6
4
3
7
2
1
5
6
4
9
2
7
8
3
4
9
8
7
3
2
5
3
2
7
8
4
4
3
7
2
2
5
9
1
4
3
7
7
2
3
5
4
COLUMN 1
2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
ROW
FIGURE 3.3 Developing cant be list.
Column 1 already has 1,2,3,4,5 and 7.
Hence, the “cantbelist” for all cells in column 1 must contain these numbers. So
in column 1 we see three cells that are empty: (3,1) (7,1), and (9,1). The table below
shows this information as array values.
Cell
reference
Array reference
Value
Cell
reference
Array reference
Value
(3,1)
cantbelist(3,1,1)
1
(7,1)
cantbelist(7,1,1)
1
(3,1)
cantbelist(3,1,2)
2
(7,1)
cantbelist(7,1,2)
2
(3,1)
cantbelist(3,1,3)
3
(7,1)
cantbelist(7,1,3)
3
(3,1)
cantbelist(3,1,4)
4
(7,1)
cantbelist(7,1,4)
4
(3,1)
cantbelist(3,1,5)
5
(7,1)
cantbelist(7,1,5)
5
(3,1)
cantbelist(3,1,6)
7
(7,1)
cantbelist(7,1,6)
7
(3,1)
cantbelist(3,1,7)
blank
(7,1)
cantbelist(7,1,7)
blank
(3,1)
cantbelist(3,1,8)
blank
(7,1)
cantbelist(7,1,8)
blank
(3,1)
cantbelist(3,1,9)
blank
(7,1)
cantbelist(7,1,9)
blank